FIG. 1 depicts a schematic diagram of a portion of a typical wireless telecommunications system, which provides wireless telecommunications service to a number of wireless terminals (e.g., wireless terminals 101-1 through 101-3) that are situated within a geographic region. The heart of wireless telecommunications system 100 is Wireless Switching Center ("WSC") 120, which might also be known as a Mobile Switching Center ("MSC") or Mobile Telephone Switching Office ("MTSO"). Typically, Wireless Switching Center 120 is connected to a plurality of base stations (e.g., base stations 103-1 through 103-5) that are dispersed throughout the geographic area serviced by the system and to the local and long-distance telephone offices (e.g., local-office 130, local-office 138 and toll-office 140). Wireless Switching Center 120 is responsible for, among other things, establishing and maintaining calls between wireless terminals and between a wireless terminal and a wireline terminal (e.g., wireline terminal 150), which wireline terminal is connected to Wireless Switching Center 120 via the local and/or long-distance networks.
The geographic area serviced by a wireless telecommunications system is divided into spatially distinct areas called "cells." As depicted in FIG. 1, each cell is schematically represented by one hexagon in a honeycomb pattern; in practice, however, each cell has an irregular shape that depends on the topography of the terrain surrounding the cell. Typically, each cell contains a base station, which comprises the radios and antennas that the base station uses to communicate with the wireless terminals in that cell and also comprises the transmission equipment that the base station uses to communicate with Wireless Switching Center 120.
For example, when wireless terminal 101-1 desires to communicate with wireless terminal 101-2, wireless terminal 101-1 transmits the desired information to base station 103-1, which relays the information to Wireless Switching Center 120. Upon receipt of the information, and with the knowledge that it is intended for wireless terminal 101-2, Wireless Switching Center 120 then returns the information back to base station 103-1, which relays the information, via radio, to wireless terminal 101-2.
When digital signals are transmitted between a base station and a wireless terminal, the signals can be corrupted during transmission by noise, interference, and distortion. For example, noise can cause a radio receiver to occasionally misinterpret a received binary digit as a "0," when it was transmitted as a "1," and to occasionally misinterpret a received binary digit as a "1," when it was transmitted as a "0." Therefore, digital wireless telecommunications systems often incorporate an error detection and correction mechanism to mitigate the effects of corrupt transmissions.
Although separate error detection and correction mechanisms are provided for transmissions from a wireless terminal to a base station (the "uplink") and for transmissions from the base station to the wireless terminal (the "downlink"), the mechanisms can be identical. So for pedagogical purposes, the details of the error detection and correction mechanism for only one line, the uplink, will be discussed in this background.
FIG. 2 depicts a block diagram of the salient components of wireless terminal 101-1 and base station 103-1 in the prior art that support an error detection and correction mechanism for uplink transmissions. Wireless terminal 101-1 comprises: information source 201, channel encoder 202, and transmitter 203, and base station 103-1 comprises: receiver 204, channel decoder 205, and information destination 206.
Information source 201 is the source of a digital message signal (e.g., digitized voice, control signals, etc.) that is to be transmitted via radio to base station 103-1. The output of information source 201 is fed to channel encoder 202.
Channel encoder 202 is the mechanism that wireless terminal 101-1 employs to provide error detection and correction for uplink transmissions. Channel encoder 202 typically partitions the digital message signal into fixed-length blocks and substitutes in the place of each block a codeword that is transmitted in place of the block. Typically, the codeword is uniquely associated with the fixed-length block and the codeword is selected from a set of error correcting codewords that are constructed in such a way as to be distinguishable even if corrupted during transmission.
In accordance with a given set of error correcting codes, channel encoder 202 substitutes each n-bit block of the digital message signal with a m-bit codeword that is uniquely associated with the n-bit block (where m&gt;n). Where the number of symbols or bits in the codeword is an integral multiple of the number of symbols or bits in the block, the symbols in the codeword are sometimes called "chips" rather than "bits," but in either case the mechanism is the same.
For example, in accordance with one error correcting code set in the prior art, the 7-4 Hamming Code, each 4-bit block of digital message signal is replaced with a 7-bit codeword that is transmitted in place of the 4-bit block. Table 1 depicts the mapping of the 4-bit blocks to 7-bit codewords in accordance with the 7-4 Hamming Code.
TABLE 1 ______________________________________ The Hamming (7-4) Code codeword index 4-bit block 7-bit codeword ______________________________________ 0 0000 0000000 1 0001 0001111 2 0010 0010110 3 0011 0011001 4 0100 0100101 5 0101 0101010 6 0110 0110011 7 0111 0111100 8 1000 1000011 9 1001 1001100 10 1010 1010101 11 1O11 1011010 12 1100 1100110 13 1101 1101001 14 1110 1110000 15 1111 1111111 ______________________________________
Channel encoder 202 then feeds each codeword, in succession, to transmitter 203, which modulates the codeword onto a carrier and transmits it to receiver 204 in base station 103-1.
Receiver 204 demodulates the incoming carrier signal and provides the (potentially corrupt) codeword to channel decoder 205 for decoding.
Channel decoder 205 is the mechanism that base station 103-1 employs to provide error detection and correction for uplink transmissions. Channel decoder 205 receives the codeword and attempts to correlate it to one of the codewords in the error correcting code set. If there is an identical match, which suggests that the codeword is not corrupt, channel decoder 205 outputs the n-bit block corresponding to the codeword. If there is no identical match, which indicates that the codeword is corrupt, channel decoder 205 attempts to correlate the corrupt codeword to the most similar codeword in the error correcting code set. When channel decoder 205 has correlated the corrupt codeword to a legitimate codeword, channel decoder 205 outputs the n-bit block corresponding to the legitimate codeword most similar to the corrupt codeword.
If (1) the error correcting code set and (2) the mechanism for correlating corrupt codewords with legitimate codewords is well constructed, an error detection and correction mechanism can all but eliminate the effects of noise, interference, and distortion on the transmission channel.
An error correction and detection mechanism in the prior art that is especially well-suited for use with code-division multiple access ("CDMA") uses an error correcting code set based on Walsh Codes. See, for example, Gilhousen et. al., "On the Capacity of a Cellular CDMA System," IEEE Trans. on Vehicular Technology, Vol. 40, pp. 303-312 (May 1991). Furthermore, U.S. Pat. Nos. 3,701,143 and 3,795,864 teach how to make and use Walsh codes for error detection and correction and are incorporated by reference as if set forth in their entirety.
In accordance with this mechanism, channel decoder 202 substitutes each n-bit block of digital message signal with a 2.sup.n -chip bipolar codeword. Because the Walsh codes are advantageously transmitted using direct-sequence spread-spectrum modulation, each symbol in a Walsh code is represented in bipolar format, whose symbols comprises "-1" and "+1,"in contrast to the symbols "0" and "1." For example, Table 2 depicts a mapping of 3-bit blocks to 8-chip Walsh codes.
TABLE 2 ______________________________________ codeword index 3-bit block 8-chip Walsh codeword ______________________________________ 0 000 +1, +1, +1, +1, +1, +1, +1, +1 1 001 +1, -1, +1, -1, +1, -1, +1, -1 2 010 +1, +1, -1, -1, +1, +1, -1, -1 3 011 +1, -1, -1, +1, +1, -1, -1, +1 4 100 +1, +1, +1, +1, -1, -1, -1, -1 5 101 +1, -1, +1, -1, -1, +1, -1, +1 6 110 +1, +1, -1, -1, -1, -1, +1, +1 7 111 +1, -1, -1, +1, -1, +1, +1, -1 ______________________________________
For example, if channel encoder 202 encodes the 3-bit block "000" as:
TABLE 3 ______________________________________ chip chip chip chip chip chip chip chip 1 2 3 4 5 6 7 8 ______________________________________ +1 +1 +1 +1 +1 +1 +1 +1 ______________________________________
corruption in transmission can cause receiver 204 to receive and output to channel decoder 205 the corrupt codeword
TABLE 4 ______________________________________ chip chip chip chip chip chip chip chip 1 2 3 4 5 6 7 8 ______________________________________ +0.92 +1.04 +0.34 +0.56 -0.23 +0.35 +0.87 +0.71 ______________________________________
One technique that channel decoder 205 can use to correlate corrupt Walsh Code codewords to legitimate codewords involves the well-known Fast Hadamard Transform. U.S. Pat. Nos. 3,859,515, 3,742,201, 3,792,355, 3,956,619 and 5,357,454, which are incorporated by reference as if set forth in their entirety, teach how to make the Fast Hadamard Transform and how to use it to correlate corrupt Walsh Code codewords to legitimate Walsh Code codewords.
The Fast Hadamard Transform accepts as input a received 2.sup.n -chip Walsh codeword, such as that in Table 4, and outputs 2.sup.n correlation signals, such as that in Table 5. Each correlation signal indicates the likelihood that the received corrupt codeword is one of the legitimate codewords. For example, a Fast Hadamard Transform performed on the corrupt codeword in Table 4 yields the correlation signals in Table 5.
TABLE 5 ______________________________________ Codeword Correlation Index Coefficient Signal ______________________________________ 1 4.96 2 1.56 3 2.12 4 -0.80 5 -0.24 6 1.24 7 -0.32 8 -1.16 ______________________________________
From Table 5, it can be seen that the correlation signal for codeword #1 is greater than that for any other codeword, and, therefore, the Fast Hadamard Transform suggests that the Walsh Code associated with codeword #1 is the most likely to have been transmitted. On that basis, channel decoder 205 outputs the 3-bit block associated with codeword #1, which from Table 2 is "000."
Although many techniques for implementing the Fast Hadamard Transform are well-known in the prior art, those techniques are generally too slow or require too much hardware for implementation in contemporary radio receivers. Therefore, the need exists for a technique that is fast, compact, and well-suited for implementation in application-specific integrated circuits.